package algorithm.hashtable;

import java.util.HashSet;
import java.util.Set;

/**
 * 217. Contains Duplicate
 * Leetcode: https://leetcode.com/problems/contains-duplicate/
 * Difficulty: Easy
 * Related Topics: Array, HashTable
 *
 * 给一个数组，判断这个数组中是否包含重复数字。
 *
 * 未写出的解法：
 * 1）使用 Arrays.sort(nums) 排序之后，判断相邻元素是否有相同的。时间复杂度O(N), 空间复杂度O(1)
 *
 * Created by yzy on 2019-05-05 18:33
 */
public class ContainsDuplicate {


    /**
     * 最简单直接的方式,利用HashSet
     * 时间复杂度：O(N)
     * 空间复杂度：O(N)
     *
     * runtime: 6ms (beats 82.54%)
     * memory: 45.5MB (beats 5.03%)
     *
     * @param nums
     * @return
     */
    public static boolean containsDuplicate(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for(int i=0; i<nums.length; i++){
            boolean succ = set.add(nums[i]);
            if(!succ){
                return true;
            }
        }
        return false;
    }
}
